A large number of image segmentation methods are known. Those methods are generally region oriented, clustering oriented, or edge oriented. Those methods are either based on concepts of similarity or discontinuity of feature values, e.g., intensities or colors, of individual pixels (points) in the image.
A region linkage oriented segmentation method ‘grows’ regions that have homogeneous intensity or color features. That method starts from an initial ‘seed’ point or pixel. The region is extended by one pixel at a time. An adjacent pixel is added to the region when a feature distance between the adjacent pixel and the region is less than a predetermined threshold. The linkage method has usually no control over a shape of a current boundary of the region as determined by the thresholding.
Histogram oriented methods attempt to remedy a number of deficiencies of simple thresholding. Additionally, histogram segmentation compensates for shifts in mean intensity level because an image intensity histogram distribution is considered, rather than examining intensity values of individual pixels directly, as in region linkage above. However, histogram segmentation has no explicit notion of connectivity. An implicit assumption is that pixels with similar intensities belong to the same region. This may not be true in general.
Edge-based segmentation takes into account that edges are usually boundaries between segments. Edges are detected by searching for local discontinuities in image features. Then, a tracing process is applied to link edges into continuous and connected segment boundaries. Edge linking techniques suffer from a number of problems. Not only must edge pixels be linked into edge lists, but these lists must also be linked so as to extract closed region boundaries. The closure problem is not straightforward to solve, because many edges may terminate in the same location or large gaps may need to be bridged between edges. Detected edges can often not form a set of closed curves, which surround connected regions.
It is desired to address the disadvantages of the above segmentation methods.
Level sets provide a general framework for modeling surface wavefront propagation, Sethian, “An analysis of flame propagation,” Ph.D. Dissertation, Mathematics, University of Berkeley, 1982, and Sethian, “Curvature and evaluation of wavefronts,” Commun. in Mathematical Physics, Vol. 101, pp. 487-499, 1985
Level sets have been used to track moving wavefront interfaces in a large number of different applications, from fluid mechanics to computer vision, Osher et al., “Fronts propagating with curvature dependent speed: Algorithms based on Hamilton-Jacobi formulation,” Journal of Computational Physics, Vol. 79, pp. 12-49, 1988, Koepfler et al., “A multiscale algorithm for image segmentation by variational method,” SIAM J. of Num. Analysis, 31-1, pp. 282-299, 1994, Malladi et al., “Shape modeling with wavefront propagation: a level set approach,” IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 17, pp. 158-175, 1995, Faugeras et al., “Variational Principles, Surface Evolution, PDE's, level set methods and the Stereo Problem,” IEEE Transactions on Image Processing, Vol. 7, No. 3, pp 336-344, 1998, Siddiqi et al., “A Hamiltonian Approach to the Eikonal Equation,” Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition, 1999, Droske et al., “A multilevel segmentation method,” Proc. Vision, Modeling and Visualization, MPI Informatik, Germany, pp. 327-336, 2000, Leventon et al., “Level Set Based Segmentation with Intensity and Curvature Priors,” IEEE Workshop on Mathematical Methods in Biomedical Image Analysis, 2000, Vemuri et al., “A Level-Set Based Approach to Image Registration,” IEEE Workshop on Mathematical Methods in Biomedical Image Analysis, 2000, Paragios et al., “Geodesic active regions and level set methods for supervised texture segmentation” International Journal of Computer Vision, Vol. 46, pp 223, 2002, and Chan et al., “Variational PDE Models in Image Processing,” Notices of the American Mathematical Society, 2003.
Prior to level sets, a motion of a curve, a boundary, or a ‘wavefront’ was represented typically by a discrete parameterization of an object as a set of points. Positions of the points are updated according to a given evolution equation using, for example, snakes, string methods, and marker particles. However, those Lagrangian techniques rely on a continual reparameterization of the surface as the surface becomes more complex. Those methods also tend to disintegrate as a topology of an evolving shape changes.
Level sets use a totally different model to represent moving wavefronts. The level set method views the wavefront propagation as a Eulerian, initial value partial differential equation. The moving wavefront is regarded as a zero level set of higher dimensional function. The evaluation of this higher dimensional function resembles a Hamilton-Jacobi equation, which enables the forming of sharp surface gradients and the incorporation of curvature effects into the propagation of the wavefront.
Prior art image segmentation suffers from either requiring a priori information to initialize regions, being computationally complex, or failing to establish the color consistency and spatial connectivity at the same time. Therefore, it is desired to provide a method, based on level sets, for partitioning an image into homogeneous segments according to some consistency criterion, e.g., color or intensity.